The invention relates to a process for coding a sequence of elements, preferably for generating the Lempel/Ziv code for such a sequence of elements.
An A. Lempel and J. Ziv code is frequently used for reducing the redundancy of a sequence of, for example, coefficients of a discrete cosine transform for image values of picture elements of a reproduced image, preferably of a medical diagnostics image, for example of an X-ray image.
The authors Abraham Lempel and Jakob Ziv describe in the journal IEEE Transactions on Information Theory, Vol. IT-23, May 1977, in an article entitled "A Universal Algorithm for Sequential Data Compression" a coding of a sequence of elements. As agreed upon, the coding and decoding cooperate here. During the coding, the sequence of elements to be coded is processed sequentially element by element. In each case here, one of the elements or, respectively, a plurality of the elements are treated as a partial sequence. Accordingly, each of the partial sequences consists of at least one of the elements. Each of the partial sequences can be extended by an added element to form a further one of the partial sequences. As agreed upon, at the beginning of the coding, for each agreed element of a set of elements, which is also frequently referred to as the alphabet, in each case one partial sequence is known, consisting in each case of exactly one of the elements. These partial sequences known at the beginning are frequently also referred to as the primary partial sequences. A code consisting of code words which form a sequence of code words is generated as the result of the coding. In this case each code word corresponds to one partial sequence in each case. At the beginning of the coding, and likewise at the beginning of the decoding, in each case one agreed code word is assigned to each element of the set of elements, and hence also assigned to each primary partial sequence. These code words are frequently also referred to as the primary code words.
Beginning with the first element of the sequence of elements to be coded, the primary partial sequence for this element is recognized and the code word assigned to it is entered in the code as first code word of the code. After this the following element of the sequence of elements to be coded is processed. After a partial sequence has been recognized in each case, the following element is processed in two respects. Firstly the last partial sequence recognized is extended by this element to form an extended new recognized partial sequence, to which a following code word is assigned. This code word is here the next one in a sequence agreed for this purpose. And secondly, for searching for subsequent partial sequences, this element extending the partial sequence is used as the first element for the subsequent partial sequences to be searched for. In each case one partial sequence consisting of as many as possible directly successive elements, for which a code word has already been assigned, is searched for.
In his article "How to quadruple dial-up communications efficiency", Mini-Micro Systems, Vol. 21, No. 2, February 1988, Newton, Mass., USA, pp. 77-81, F. Bacon gives a general description of the Lempel/Ziv process for coding temporal sequences of elements of an alphabet. A coding process, the so-called Telcore model, is described in this paper by F. Bacon, which is to be understood as the connection of the Lempel/Ziv process with the Huffman coding. This process is not suitable for the generation of the Lempel/Ziv code, neither is it otherwise compatible with Lempel/Ziv codes. A contribution to the achieving of the object on which the present patent application is based cannot be found in the publication by F. Bacon. In particular, no reference is made to a process for code generation which avoids a searching for code words.
During the coding, in each case the entire list of the previously recognized partial sequences must be searched through here. The code word which is assigned to the longest of these partial sequences is entered in the code. After this, on the one hand this partial sequence is likewise extended with the element following this partial sequence, and on the other hand the search for following partial sequences commences.
During the decoding, the assigned partial sequences for the code words are decoded. In this case the respective partial sequence is likewise extended in each case by the immediately following element to form a recognized extended partial sequence. For this purpose, likewise a following code word is assigned in each case, which can likewise be assigned in accordance with the sequence agreed for this purpose.
With each extended partial sequence, therefore, the list of previously recognized partial sequences is also lengthened. The list to be searched through in each case is therefore constantly growing. As a consequence, the coding is constantly slowed down too.